home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / tsql / doc / tsql.mail / 000039_atuzhili@squar….stern.nyu.edu _Tue Mar 16 14:40:27 1993.msg < prev    next >
Internet Message Format  |  1996-01-31  |  4KB
  1. Received: from SQUARE1.STERN.NYU.EDU by optima.cs.arizona.edu (5.65c/15) via SMTP
  2.     id AA16071; Tue, 16 Mar 1993 12:38:16 MST
  3. Received: by square1.stern.nyu.edu (4.1/1.34)
  4.     id AA04330; Tue, 16 Mar 93 14:40:27 EST
  5. Date: Tue, 16 Mar 93 14:40:27 EST
  6. From: atuzhili@square1.stern.nyu.edu (Alexander Tuzhilin)
  7. Message-Id: <9303161940.AA04330@square1.stern.nyu.edu>
  8. To: tsql@cs.arizona.edu
  9. Subject: Benchmark initiative
  10.  
  11.  
  12. We would like to make two comments on the proposal to develop a
  13. comprehensive set of natural language queries as a test of "goodness"
  14. of various query languages and algebras.
  15.  
  16. First, we feel that a certain classification of various queries has to
  17. be established before the set of queries is proposed.  As an *initial*
  18. suggestion, we can classify temporal queries as follows.
  19.  
  20.          | HISTORICAL     | ROLLBACK  | BITEMPORAL
  21. --------------------------------------------------------
  22. UNGROUPED     |        |        |
  23.          |        |        |
  24. GROUPED         |        |        |
  25.          |        |        |
  26. TEMP. AGGREGATES |        |        |
  27.          |        |        |
  28. SCHEMA VERSIONING|        |        |
  29.          |        |        |
  30. OTHER FEATURES     |        |        |
  31. --------------------------------------------------------
  32.  
  33. Then we can place one or several queries in each cell of this matrix.
  34.  
  35. We want to stress that this is only an *initial* proposal to classify
  36. various temporal queries which should be elaborated further.  Perhaps,
  37. the two-dimensional matrix is not sufficient.  Perhaps, this matrix
  38. should be reorganized as a three-dimensional cube
  39. (historical/rollback/bitemporal is one dimension, grouped/ungrouped
  40. another, and temporal aggregates and schema versioning the third).
  41. Perhaps, it can be an n-dimensional cube.
  42.  
  43. The second comment is that the development of the benchmark should not
  44. be a substitute for a rigorous *theoretical* study of expressive
  45. powers of various temporal query languages and algebras.  It is not
  46. entirely clear what the goal of the benchmark is.  What seems
  47. necessary is a kind of typography of temporal data models as suggested
  48. by the above table and discussion.  For example, one data model can be
  49. grouped bitemporal, another be ungrouped historical with aggregates.
  50. Perhaps, the benchmark can be useful in developing such a typography.
  51. Each type of data model should support a class of queries the model
  52. embodies and should have its own standard of completeness.  We believe
  53. that this standard should be developed in the terms of an appropriate
  54. logic (as in the classical relational case) rather than trying to
  55. determine expressive power "by consensus" (we would not want to say
  56. that one language is more expressive than another if it can express
  57. 95% of the benchmark queries and the other one only 87%).
  58.  
  59. We addressed this issue in our paper "On Completeness of Historical
  60. Relational Query Languages" (Working Paper IS-91-41 from Stern School
  61. of Business, NYU; also to appear in TODS) where we proposed a measure
  62. of completeness of various query languages.  We introduced and
  63. disussed the semantic difference between grouped and ungrouped data
  64. models and explained the difference between queries on grouped and
  65. ungrouped temporal data models. For the ungrouped temporal data
  66. models (e.g. TQuel), we proposed to use either temporal logic, or
  67. first-order logic with explicit references to time, or the temporal
  68. algebra TA (proposed in the paper "A Temporal Relational Algebra as a
  69. Basis for Temporal Relational Completeness" (Tuzhilin & Clifford,
  70. VLDB'90)), all of which have the same expressive power for the
  71. discrete linear models of time, as a basis for the ungrouped temporal
  72. completeness.  For the grouped models (e.g. Gadia, Tansel, HRDM), we
  73. proposed to use the calculus L_h that we defined in that paper.  We
  74. also examined completeness of various temporal query languages and
  75. algebras proposed in the literature.
  76.  
  77. We invite comments and discussion of these issues from the temporal
  78. database community.
  79.  
  80. Jim Clifford
  81. Al Croker
  82. Alex Tuzhilin
  83.